package projet;

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;

public class MainGraphe {
	static int NON_ATTEINT=-1;
	static int ATTEINT=0;
	static int TRAITE=1;

	static ListeChainee circuitEulerian=new ListeChainee();

	public static boolean isthme(GrapheListe F,int sommet,int sommetVoisin){
		boolean isthm=false;
		if (F.sommets.get(sommet).listeSommets.size()>1 && F.sommets.get(sommetVoisin).listeSommets.size()==1) {
			return true;
		}		
		if (F.sommets.get(sommet).listeSommets.size()<2) {
			
			isthm=false;
			return isthm;
		}
		else{
			GrapheListe g;
			g = F.copierGraphe();
			g.enleveArete(sommet, sommetVoisin);
			int etat[],pere[],sigma[];
			etat= new int[F.getNbSommets()];
			pere= new int[F.getNbSommets()];
			sigma= new int[F.getNbSommets()];
			for (int i = 0; i < etat.length; i++) {
				etat[i]=NON_ATTEINT; //non_atteint
			}	
			int index=1;
			Queue<Integer> a_traiter=new LinkedList<Integer>();//null
			int z=sommet;
//			while(g.sommets.get(z) != null){
			
			for (Iterator iterator = g.sommets.get(z).listeSommets.iterator(); iterator.hasNext();) {
				z = (Integer) iterator.next();
				pere[z]=Integer.MAX_VALUE;//<-null
				sigma[z] = index;
				index++;
				a_traiter.add(z);
				int x;
				while(a_traiter.size()!=0){
					x = a_traiter.peek();
					if(x == sommetVoisin){
						isthm=false;
						return isthm;
					}
					for (Iterator ite = g.sommets.get(x).listeSommets.iterator(); ite.hasNext();) {
						Integer y = (Integer) ite.next();
						if (etat[y] == NON_ATTEINT) {
							etat[y] = ATTEINT; //atteint
							sigma[y]=index;
							index++;
							a_traiter.add(y);
						}
					}
					a_traiter.poll();
					etat[x]=TRAITE;
				}
			}	
		}
		return isthm;
	}

	public static String Fleury(GrapheListe G, int u){
		String C="";
		C += u+" ";
		circuitEulerian.ajouterSommet(u);
		int x = u;
		GrapheListe F = G.copierGraphe();
		
		Iterator<Integer> iterator;
		int y=Integer.MIN_VALUE;
		while(F.existeAretesIncidentes(x)){
			
			for (Iterator<Integer> iterator2 = F.sommets.get(x).listeSommets.iterator(); iterator2.hasNext();) {
				y = (int) iterator2.next();
				
				if(!isthme(F,x,y)){
					
					F.enleveArete(x,y);
					x = y;
					C += y+" ";
					circuitEulerian.ajouterSommet(y);
					break;
				}
			}
			
		}
		return C;
	}	

	public static void main(String[] args) {
		Scanner scanner = new Scanner(new BufferedInputStream(System.in));
		int n= scanner.nextInt();
		
		GrapheListe graphe= new GrapheListe(n);
		for(int i=0;i<n;i++){
			String voisin = scanner.next();
			while(true){
				if(voisin.equals("-1"))
					break;

				graphe.ajoutArete(i,Integer.parseInt(voisin));
				voisin=scanner.next();
			}
		}
		
		System.out.print("Sommet de Depart entre 0 et "+(n-1)+":");
		n= scanner.nextInt();
		
		MainGraphe.Fleury(graphe, n);
		System.out.println("circuitEulerian: "+MainGraphe.circuitEulerian.toString());
		
	}

}
